package Demo1_14;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-01-14
 * Time:21:57
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

public class PalindromeLinkedList {
    public boolean chkPalindrome(ListNode A) {
        if (A == null || A.next == null) {
            return true;
        }
        // 使用快慢指针找到中间节点
        ListNode slow = A;
        ListNode fast = A;
        while (fast!= null && fast.next!= null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 反转后半部分链表
        ListNode prev = null;
        ListNode curr = slow;
        while (curr!= null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        // 比较前半部分和反转后的后半部分
        ListNode p1 = A;
        ListNode p2 = prev;
        while (p2!= null) {
            if (p1.val!= p2.val) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }

    public static void main(String[] args) {
        // 构建测试链表 1->2->3->2->1
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(1);
        PalindromeLinkedList solution = new PalindromeLinkedList();
        System.out.println(solution.chkPalindrome(head));
    }
}
